/* 474. 一和零 */
/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

/* 
    三维dp
    dp[i][j][k] 表示前i个字符串中 使用j个0 k个1 的情况小最多得到的
    字符串数量 

    当没有任何字符串可以使用时，可以得到的字符串数量只能时0
    因此动态规划的边界条件是: 
    当 i = 0 时，对任意 0 <= j <= m 和 0 <= k <= n  都有 dp[i][j][k] = 0

    当 1<= i <= l 对于strs 中的第i个字符串，首先遍历该字符串得到其中0和1的数量
    分别记为 zeros 和 ones 然后对于 0 <= j <= m 和 0 <= k <= n 计算dp[i][j][k]的值
    如果 j < zeros 或 k < ones 则不能选第i个字符串 此时有 dp[i][j][k] = dp[i-1][j][k]
    如果 j >= zeros 且 k >= ones 则如果不选 第i个字符串 有 dp[i][j][k] = dp[i-1][j][k]
    如果选第i个字符串，有dp[i][j][k] = dp[i-1][j-zeros][k-ones] + 1





*/
var findMaxForm = function (strs, m, n) {
	const length = strs.length
	const dp = new Array(length + 1)
		.fill(0)
		.map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)))

	for (let i = 1; i <= length; i++) {
		const zerosOnes = getZerosOnes(strs[i - 1])
		let zeros = zerosOnes[0],
			ones = zerosOnes[1]
		for (let j = 0; j <= m; j++) {
			for (let k = 0; k <= n; k++) {
				dp[i][j][k] = dp[i - 1][j][k]
				if (j >= zeros && k >= ones) {
					dp[i][j][k] = Math.max(
						dp[i - 1][j][k],
						dp[i - 1][j - zeros][k - ones] + 1
					)
				}
			}
		}
	}
	return dp[length][m][n]
}
/* 
    滚动数组
    内层循环采用倒序遍历的方式 这种方式保证转移来的是 dp[i-1][j][k] 中的元素
*/

var findMaxForm = function (strs, m, n) {
	const dp = Array.from({ length: m + 1 }, () => new Uint8Array(n + 1))
	const length = strs.length
	for (let i = 0; i < length; i++) {
		const zerosOnes = getZerosOnes(strs[i])
		const zeros = zerosOnes[0],
			ones = zerosOnes[1]

		for (let j = m; j >= zeros; j--) {
			for (let k = n; k >= ones; k--) {
				dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1)
			}
		}
	}

	return dp[m][n]
}
const getZerosOnes = (str) => {
	const zerosOnes = new Array(2).fill(0)
	const length = str.length
	for (let i = 0; i < length; i++) {
		zerosOnes[str[i].charCodeAt() - '0'.charCodeAt()]++
	}
	return zerosOnes
}
const ans = findMaxForm(['10', '0', '1'], 1, 3)
console.log('ans :>>', ans)
